package MyTree;

import java.util.ArrayList;
import java.util.List;

public class Leetcode0113 {
    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<>();
        int cnt = 0;

        dfs(root, targetSum, cnt, path, res);
        return res;
    }

    public static void dfs(TreeNode root, int targetSum, int cnt, List<Integer> path, List<List<Integer>> res){
        System.out.println(path.toString());
        if (root == null){
            return;
        }
        cnt += root.val;
//        if(cnt > targetSum){
//            return;
//        }
        List<Integer> newPath = new ArrayList<>(path);
        newPath.add(root.val);
        if(root.left != null){
            dfs(root.left, targetSum, cnt, newPath, res);
        }
        if(root.right != null) {
            dfs(root.right, targetSum, cnt, newPath, res);
        }
        if(root.left == null && root.right == null){
            if(cnt == targetSum){
                res.add(newPath);
            }
            return;
        }
    }

}
